#define DEBUG
#include <cstdio>
#ifdef DEBUG
#define MAXM 1000000
#else
#define MAXM 1000000
#endif

using namespace std;

int main() {
#ifdef DEBUG
  freopen("2.in", "r", stdin);
  freopen("2.out", "w", stdout);
#endif

  int t;
  scanf("%d", &t);
  static char s[3][MAXM+1];
  int n, m;
#ifdef DEBUG
  for (n=1; n<=10; n++) {
    printf("%d:\n", n);
    for (m=1; m<=40; m++) {
#endif
  for (int ti=1; ti<=t; ti++) {
#ifndef DEBUG
    scanf("%d %d", &n, &m);
#endif
    s[1][0] = 'a', s[1][1]='\0';
    s[2][0] = 'b', s[2][1]='\0';
    for (int i=3; i<=n; i++) {
      int len=0;
      for (int j=0; len<m && s[(i-1)%3][j]!='\0'; j++) {
	s[i%3][len++] = s[(i-1)%3][j];
      }
      for (int j=0; len<m && s[(i-2)%3][j]!='\0'; j++) {
	s[i%3][len++] = s[(i-2)%3][j];
      }
      s[i%3][len] = '\0';
    }
    int i;
    bool flag=false;
    for (i=m; i>0 && !flag; ) {
      i--;
      flag = true;
      for (int j=0; j<i && flag; j++) {
	flag = s[n%3][j]==s[n%3][m-i+j];
      }
    }
    printf("%d\n", i);
  }
#ifdef DEBUG
    }
  printf("\n");
  }
#endif

  fcloseall();
  return 0;
}
